C. Boring Day

Egor 有一副 n 的扑克牌,最上面的那张 i 写着数字 ai 。Egor 想玩一定轮数的游戏,直到牌用完为止。在每一轮中,他都会从牌面顶端抽取一张非零数的牌,然后结束这一轮。如果在这一轮中收集到的纸牌上的数字之和在 lr 之间(含),则这一轮获胜;否则,这一轮失败。

埃戈尔对纸牌的顺序了如指掌。请帮助 Egor 确定他在这样的游戏中最多可以赢多少轮。请注意,伊戈尔不需要连续赢几轮。

我发现这种思想(双指针/简单 DP 思想)我基本每次都想不到... 多练吧

贪心:双指针

#define int long long
void solve() {
    int n, l, r;cin >> n >> l >> r;
    vector<int> a(n);
    for (int i = 0;i < n;i++)cin >> a[i];

    int ans = 0, cur = 0, L = 0, R = 0;
    while (L < n) {
        while (R < n && cur < l) {
            cur += a[R];R++;
        }
        if (l <= cur && cur <= r) {
            ans++;L = R;cur = 0;
        } else {
            cur -= a[L];L++;
        }
    }
    cout << ans << '\n';
}

DP

#define int long long
void solve() {
    int n, l, r;cin >> n >> l >> r;
    vector<int> a(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    vector<int> dp(n + 1);
    int s = 0;
    int j = -1;
    for (int i = 0; i < n; i++) {
        dp[i + 1] = max(dp[i + 1], dp[i]);
        if (j < i) {
            j = i;
            s = 0;
        }
        while (j < n && s < l) {
            s += a[j++];
        }
        if (s >= l && s <= r) {
            dp[j] = max(dp[j], dp[i] + 1);
        }
        s -= a[i];
    }

    cout << dp[n] << '\n';
}